\begin{abstract}
\section*{Abstract}
This report describes a solver for the Sokoban game.

A Sokoban board is a labyrinth with walls, some boxes and some goals. To solve the board all boxes have to be pushed on a goal.

The chosen approach to find a solution creates a tree with all possible pushes on this board. Because searching this tree is not possible in a given time period, different improvements try to prune the tree efficiently to reduce the calculation of branches. These improvements take into account duplicated boards, deadlocks, valued fields and tunnels.

The final solution that we presented could solve around 80 boards under 1 minute. As long as the agent could give a solution inside the given time, that solution would be a correct one.

The main problem encountered was the poor optimality of the algorithms, which resulted in not being able to solve some boards because of lack of time and/or memory. Also, the encoding of two different approaches, one for the milestone and one for the final solution, implied that we spent a very long time coding. This left little time to analyse our algorithms for optimizations.
\end{abstract}
\newpage